#if !defined(__AC3_H)
#define __AC3_H 1

#include <stdlib.h>
#include <stdio.h>
#include <list>

#include "urbcsp.h"

// 

// This file includes

// here we define the AC algorithms used by the BT class.
// AC_CLASS can be 'CSP_Ac3', 'CSP_Ac4', 'CSP_Ac6' etc. 
// They can be defined in the command line of compiler
// with -DAC_CLASS=CSP_Ac3 .... (To undefine is -UAC_CLASS ...)
// Currently they are defined in the mac#.cpp for corresponding
// mac algorithms
#define AC_CLASS CSP_Ac3

#ifdef USEAC311
//#warning Using AC3.1.1
#define AC ac3_1_1
#define MAC mac3_1_1
#define RESTORE_MAC restoreMAC3_1_1
#endif

#ifdef USEAC31
//#warning Using AC3.1
#define AC ac3_1
#define MAC mac3_1
#define RESTORE_MAC restoreMAC3_1
#endif


#ifdef USEAC31R
//#warning Using AC3.1
#define AC ac3_1_residue
#define MAC mac3_1_residue
#define RESTORE_MAC restoreMAC3_1
#endif

#ifdef USEAC3
//#warning Using AC3
#define AC ac3
#define MAC mac3
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3R
//#warning Using AC3R
#define AC ac3_residue
#define MAC mac3_residue
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3DR
//#warning Using AC3R
#define AC ac3_residueD
#define MAC mac3_residueD
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3ADR
//#warning Using AC3R
#define AC ac3_AresidueD
#define MAC mac3_AresidueD
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3RDR
//#warning Using AC3R
#define AC ac3_RresidueD
#define MAC mac3_RresidueD
#define RESTORE_MAC restoreMAC3
#endif


#ifdef USEAC3FDR
//#warning Using AC3R
#define AC ac3_FresidueD
#define MAC mac3_FresidueD
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3DFR
//#warning Using AC3R
#define AC ac3_DFresidueD
#define MAC mac3_DFresidueD
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3SFR
//#warning Using AC3R
#define AC ac3_SFresidueD
#define MAC mac3_SFresidueD
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3AFDR
//#warning Using AC3R
#define AC ac3_AFresidueD
#define MAC mac3_AFresidueD
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3C
//#warning Using AC3C
#define AC ac3_cache
#define MAC mac3_cache
#define RESTORE_MAC restoreMAC3
#endif

#ifdef USEAC3ADO

#define AC ac3_ADO
#define MAC mac3_ADO
#define RESTORE_MAC restoreMAC3
#endif


// AC is the method name of the AC algorithm
// It should inlude INiTIALIZING the control structure of
// the corresponding algorithm AND ENFORCING arc consistency
// of the csp: AC_init() + MAC
// #define AC ac3
// #define AC ac3_cache
// #define AC ac3_residue
// #define AC ac3_1
// #define AC ac3_1_1

// THe method to propogate the impact of the instantiation of
// variable. MAC can be MAC3, MAC4, MAC5, etc.
// #define MAC mac3
// #define MAC mac3_cache
// #define MAC mac3_residue
// #define MAC mac3_1
// #define MAC mac3_1_1

// This is the recover method to restore the 
// internal state of an AC algorithm
// restoreMAC3 is used by mac3cache and mac3residue
// #define RESTORE_MAC restoreMAC3
// #define RESTORE_MAC restoreMAC3_1
// #define RESTORE_MAC restoreMAC3_1_1

using namespace std;

// Queue operation
class FilterQueue {
  struct Qentry {int i,j; } ;
  Qentry *Q;
  int *status;
  int head, tail;
  int n; // used to identify the position of (i,j) in status
  int length;

 public:
  FilterQueue(int n);
  ~FilterQueue();
  int empty() {  if (head == tail) return 1; else return 0; }
  void enqueue(int);
  void dequeue(int &);
};

// AC enforcing

typedef char* ConstraintCache; // single constrain

class CSP_Ac3 : public CSP {
 private:
  void initCSP_Ac3();

 protected:
  bool autofail;
  // FilterQueue Q; 
  
  //---------------- permanent data ------------------
  // for AC3.0 and AC3.1 no permanent control structure is necessary. 
  // statistics: num_checks defined in csp.h
  int numOfRemovedValuesB4Propogation; 

  // for AC3_cache. cnCache is the FULL
  // cache of the constraint network
  ConstraintCache* cnCache; 

  // this is for mac3.1.1
  // firstRvision[i][j] is true if it is the first time to
  // revise c_{ij}, false otherwise.
  bool *firstRevision; 
  // stopValues[i][j][x-1] is the last value to check in finding
  // the support for x. 
  int  *stopValues;

#ifdef TAIL_DOMAIN
  bool *supportB4StopValue;
#endif

#ifdef ADAPTIVE_DOMAIN
  SupportNode ***mac3ado_support;
#endif


  //---------------- data needs to be maintained ----
  // no control data is maintained in AC3
  // no control data is maintained in mac3.1.1

  // Support for ac3.1
  typedef int* Support;
  // support((i,a),j): the support of (i,a) in D_j
  Support *support;
  Support *resD;

  Support *fit1;
  Support *fit2;


  // the list previousSupports is to remember the 
  // support of a var.value.
  typedef struct{
    int varI, varJ;
    int value; // value is for varI
    int support;
    int phase;
  } BackupedSupport; 
  stack<BackupedSupport> previousSupports;
  #ifdef DOMAIN_SPLIT
  stack<BackupedSupport> domainSupports;
#endif

  //-------------- disposable variables -------------

  //-------------- the internal methods -------------
  // revise functions used by ac-3 like algorithms
  bool REVISE3(int, int); // for mac3
  bool REVISE3_cache(int, int); // for mac3 with cache
  bool REVISE3_residue_propogate(int, int); // for mac3 with residue
  bool REVISE3_1_init(int, int); // for mac3_1 and mac3_1_1
  bool REVISE3_1_propogate(int, int); // for mac3_1
  bool REVISE3_1_1(int, int); // for mac3_1_1
  bool REVISE3_ADO_init(int,int);
  bool REVISE3_ADO_propogate(int,int);
  bool REVISE3_residueD_init(int,int);
  bool REVISE3_residueD_propogate(int,int);
  bool REVISE3_AresidueD_propogate(int,int);
  bool REVISE3_RresidueD_propogate(int,int);
  bool REVISE3_DFresidueD_init(int,int);
  bool REVISE3_DFresidueD_propogate(int,int);
  bool REVISE3_SFresidueD_propogate(int,int);
  bool REVISE3_FDresidueD_init(int,int);
  bool REVISE3_FDresidueD_propogate(int,int);
  bool REVISE3_FresidueD_init(int,int);
  bool REVISE3_FresidueD_propogate(int,int);
  bool REVISE3_AFresidueD_propogate(int,int);
  bool REVISE3_1_residue_init(int,int);
  bool REVISE3_1_residue_propogate(int,int);
  // enqueue all neighbours
  // void enq_neighbours(int, int); 

  // these initializations return the Queue of 
  // domains to be revised
  bool ac3_init(FilterQueue& Q);
  bool ac3_cache_init(FilterQueue& Q);
  bool ac3_residue_init(FilterQueue& Q);
  bool ac3_1_init(FilterQueue& Q);
  bool ac3_ADO_init(FilterQueue& Q);
  bool ac3_residueD_init(FilterQueue& Q);
  bool ac3_1_residue_init(FilterQueue& Q);
  bool ac3_DFresidueD_init(FilterQueue& Q);
  bool ac3_FresidueD_init(FilterQueue& Q);

  // these functions propogation the impact of the 
  // revised domains in Q
  bool ac3_propogate(FilterQueue& Q); // for mac3
  bool ac3_cache_propogate(FilterQueue& Q); // for mac3_cache  
  bool ac3_residue_propogate(FilterQueue& Q); // for mac3_residue  
  bool ac3_1_propogate(FilterQueue& Q); //for mac3_1
  bool ac3_1_1_propogate(FilterQueue& Q); //for mac3_1_1
  bool ac3_ADO_propogate(FilterQueue& Q);
  bool ac3_residueD_propogate(FilterQueue& Q);
  bool ac3_AresidueD_propogate(FilterQueue& Q);
  bool ac3_RresidueD_propogate(FilterQueue& Q);
  bool ac3_DFresidueD_propogate(FilterQueue& Q);
  bool ac3_SFresidueD_propogate(FilterQueue& Q);
  bool ac3_FresidueD_propogate(FilterQueue& Q);
  bool ac3_AFresidueD_propogate(FilterQueue& Q);
  bool ac3_1_residue_propogate(FilterQueue& Q);
  
  //----------- Almost every AC should have these methods ----

  void restoreMAC3(int phase) { }; // do nothing for AC3

  // this is to restore the internal state of AC3.1
  void restoreMAC3_1(int phase);
  void restoreMAC3_1_1(int phase) { } ; // do nothing for AC3_1_1
  virtual bool isAssigned(int) = 0; 
 public:
  CSP_Ac3(int n, int d, int e, int T, int *S);
  CSP_Ac3(int n, int d); 
  CSP_Ac3(char *);
  virtual ~CSP_Ac3();

  //----------- Almost every AC should have these methods ----  
  // initialize MAC3 and make the csp arc consistent
  bool ac3();
  bool ac3_cache();
  bool ac3_residue();
  bool ac3_1();
  bool ac3_1_1();
  bool ac3_ADO();
  bool ac3_residueD();
  bool ac3_AresidueD();
  bool ac3_RresidueD();
  bool ac3_DFresidueD();
  bool ac3_SFresidueD();
  bool ac3_FresidueD();
  bool ac3_AFresidueD();
  bool ac3_1_residue();

  // assume the csp is now arc consistent. After we assign a value
  // to var, mac3(var, value) will make the new network
  // arc consistent.
  bool mac3(int var, int value); 
  bool mac3_cache(int var, int value);
  bool mac3_residue(int var, int value);
  bool mac3_1(int var, int value);
  bool mac3_1_1(int var, int value);
  bool mac3_ADO(int var, int value);
  bool mac3_residueD(int var, int value);
  bool mac3_AresidueD(int var, int value);
  bool mac3_RresidueD(int var, int value);
  bool mac3_DFresidueD(int var, int value);
  bool mac3_SFresidueD(int var, int value);
  bool mac3_FresidueD(int var, int value);
  bool mac3_AFresidueD(int var, int value);
  bool mac3_1_residue(int var, int value);

  bool mac3(int var); 
  bool mac3_cache(int var);
  bool mac3_residue(int var);
  bool mac3_1(int var);
  bool mac3_1_1(int var);
  bool mac3_ADO(int var);
  bool mac3_residueD(int var);
  bool mac3_AresidueD(int var);
  bool mac3_RresidueD(int var);
  bool mac3_DFresidueD(int var);
  bool mac3_SFresidueD(int var);
  bool mac3_FresidueD(int var);
  bool mac3_AFresidueD(int var);
  bool mac3_1_residue(int var);

  bool mac3(list<int>& var); 
  bool mac3_cache(list<int>& var);
  bool mac3_residue(list<int>& var);
  bool mac3_1(list<int>& var);
  bool mac3_1_1(list<int>& var);
  bool mac3_ADO(list<int>& var);
  bool mac3_residueD(list<int>& var);
  bool mac3_AresidueD(list<int>& var);
  bool mac3_RresidueD(list<int>& var);
  bool mac3_DFresidueD(list<int>& var);
  bool mac3_SFresidueD(list<int>& var);
  bool mac3_FresidueD(list<int>& var);
  bool mac3_AFresidueD(list<int>& var);
  bool mac3_1_residue(list<int>& var);
  virtual void statistics();
};

#endif

